package main

import "fmt"

func main() {
	height := []int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}
	fmt.Printf("trap(height): %v\n", trap(height))
}

/*
*
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
*/

/*
显而易见的是，我们得分别从两边往中间找
最高的柱子决定了上限，最高的柱子的两边决定了下限
*/
func trap(height []int) int {
	maxHeight := 0 // 最高的柱子的下标
	for i := 0; i < len(height); i++ {
		if height[i] > height[maxHeight] {
			maxHeight = i
		}
	}

	left, right, mid := 0, len(height)-1, maxHeight
	sum := 0
	tempMaxHeight := height[0]
	// 开始遍历左边的部分
	for left < mid {
		// 找到一个低点
		if height[left] < tempMaxHeight {
			sum += tempMaxHeight - height[left]
		} else {
			// 找到一个更高点
			tempMaxHeight = height[left]
		}
		left++
	}
	// 开始遍历右边的部分
	tempMaxHeight = height[right]
	for right > mid {
		// 找到一个低点
		if height[right] < tempMaxHeight {
			sum += tempMaxHeight - height[right]
		} else {
			// 找到一个更高点
			tempMaxHeight = height[right]
		}
		right--
	}
	return sum
}

func trap2(height []int) int {
	lMax, rMax := height[0], height[len(height)-1]
	left, right := 1, len(height)-2
	if len(height) <= 2 {
		return 0
	}
	sum := 0
	for left <= right {
		if lMax <= rMax {
			sum += max(0, lMax-height[left])
			lMax = max(lMax, height[left])
			left++
		} else if lMax > rMax {
			sum += max(0, rMax-height[right])
			rMax = max(rMax, height[right])
			right--
		}
	}
	return sum
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
